package org.example.day01;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO
 * 中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到第一月饼的个数是Max1，
 * 单人分到第二多月饼个数是Max2，Max1-Max2 <= 3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1) – Max(n) <= 3, 问有多少种分月饼的方法
 * @date 2024/3/11 15:22
 */
public class test007 {
    public static int countDistributionMethods(int m, int n) {
        // 初始化结果数量为0
        int count = 0;

        // 递归计算分月饼的方法种类数
        count = countDistribution(0, m, n);

        return count;
    }

    // 递归计算分月饼的方法种类数
    private static int countDistribution(int index, int m, int n) {
        // 如果所有月饼都分完了，则说明找到了一种分配方法，返回1
        if (m == 0) {
            return 1;
        }

        // 如果所有员工都分完月饼了，但还有月饼剩余，则说明这种分配方法不可行，返回0
        if (index == n) {
            return 0;
        }

        int count = 0;
        // 尝试给当前员工分配0到3个月饼
        for (int i = 0; i <= 3; i++) {
            // 如果给当前员工分配i个月饼后，剩余月饼数量小于等于当前员工的数量，并且剩余月饼数量大于等于剩余员工的数量，说明这是一种合法的分配方法
            if (m - i >= 0 && m - i <= index) {
                // 递归调用，继续向后分配月饼
                count += countDistribution(index + 1, m - i, n);
            }
        }

        return count;
    }
    public static void main(String[] args) {
        // 测试样例
        int m = 5; // 员工数量
        int n = 7; // 月饼数量

        int result = countDistributionMethods(m, n);
        System.out.println("分月饼的方法种类数为: " + result);
    }
}
